/*
 * 后缀表达式计算
 * 只支持整数合简单的运算符
 */



#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>


/******************************************************************************/

typedef int ElemType;

struct node {
    ElemType data;
    struct node *next;
};

struct link_stack {
    struct node *top;
    int count;
};
typedef struct link_stack link_stack_t;


/*
 * 初始化栈
 */
void
init_stack(link_stack_t *stack)
{
    stack->top = NULL;
    stack->count = 0;
}

int
get_stack_length(link_stack_t *stack)
{
    return stack->count;
}

int
is_stack_empty(link_stack_t *stack)
{
    return stack->count == 0;
}

int
get_stack_top_item(link_stack_t *stack, ElemType *item)
{
    if (stack->count == 0)
        return -1;

    *item = stack->top->data;

    return 0;
}


/*
 * 入栈：不需要头结点
 */
int
push(link_stack_t *stack, ElemType *item)
{
    struct node *ptr;
    ptr = (struct node *) malloc(sizeof(struct node));

    ptr->next = stack->top;
    ptr->data = *item;
    stack->top = ptr;
    ++stack->count;

    return 0;
}

/*
 * 出栈：不需要头结点
 */
int
pop(link_stack_t *stack, ElemType *item)
{
    /* if empty */
    if (stack->count == 0)
        return -1;

    struct node *ptr;
    ptr = stack->top;

    *item = ptr->data;
    stack->top = ptr->next;
    free(ptr);
    --stack->count;

    return 0;
}




/******************************************************************************/


int is_char_op(char c)
{
    switch (c)
    {
        case '+':
        case '-':
        case '*':
        case '/':
        case '(':
        case ')':
            return 1;
        default:
            return 0;
    }
}

int cal(int num1, int num2, char op)
{
    switch (op)
    {
        case '+':
            return num1 + num2;
        case '-':
            return num1 - num2;
        case '*':
            return num1 * num2;
        case '/':
            if (num2 == 0)
                return 0;
            return num1 / num2;
        default:
            return 0;
    }
}


/*
 * 后缀表达式计算
 * 规则：从左到右遍历表达式的每个数字和符号，遇到数字就进栈，遇到符号就将处于
 * 栈顶的两个数字出栈，进行运算，运算结果进栈，一直到最终获得结果。
 */
int postfix_cal(char *postfix_exp)
{
    int num, i;
    char str_num[10];
    int num_index = 0;
    int num1, num2;
    char c;
    
    link_stack_t stack;
    init_stack(&stack);
    
    memset(str_num, 0, sizeof(str_num));
    num_index = 0;
    for (i = 0; postfix_exp[i] != '\0'; ++i) {
        c = postfix_exp[i];
        
        if (isdigit(c)) {
            str_num[num_index++] = c;
            continue;
        }
        
        /* 如果不是数字 */
        if (num_index != 0) {
            /* 数字进栈 */
            num = atoi(str_num);
            push(&stack, &num);
            
            memset(str_num, 0, sizeof(str_num));
            num_index = 0;
        }
        
        /* 如果是符号，栈顶两个数字出栈并运算，结果进栈 */
        if (is_char_op(c)) {
            num1 = num2 = 0;
            pop(&stack, &num2);
            pop(&stack, &num1);
            
            num = cal(num1, num2, c);
            
            push(&stack, &num);
        }
    }
    
    /* 最后将结果出栈 */
    pop(&stack, &num);
    
    return num;
}

int main(void)
{
    int res;

    char *s1 = "9  3 1 -  3 * + 10 2 / +";
    res = postfix_cal(s1);
    printf("postfix: %s = %d\n", s1, res);

    char *s2 = "33 1 -  3 * 10 2 / +";
    res = postfix_cal(s2);
    printf("postfix: %s = %d\n", s2, res);
    
    return 0;
}


